from data_buffer import data
import time
_data = data(0)
a = 0
array = _data.array_buffer[:]
target = _data.target_buffer[:] # 目标状态

arrCopied = array.copy()  # 重置至初始状态用
count = 0  # 统计一共尝试了多少次


def name_move(arr, present, result):
    global a
    a = 1
    result_List = []
    for i in result:
        NameList = getBesides(arr, present)
        index_i = NameList.index(i)
        if index_i == 0:
            result_List.append("向上")
        elif index_i == 1:
            result_List.append("向左")
        elif index_i == 2:
            result_List.append("向右")
        elif index_i == 3:
            result_List.append("向下")

        move(arr, i, present)
        NameList = []
    return result_List


def issolution(array):
    # 判断有无解
    num = 0  # 计算除0之外的所有元素的逆序和
    for i in range(1, len(array)):
        for j in range(i):
            if array[i] == 0 or array[j] == 0:
                continue
            elif array[i] < array[j]:
                num += 1
    return num % 2


def getIndex(array: list, num: int) -> int:
    # 获取对应值的下标
    return array.index(num)


def outPut(array: list, present: int, position: str) -> int:  # 获取对应 位置(position) 的值
    index = getIndex(array, present)  # 获取当前值的下标

    # 判断输出当前值（present）的对应相邻的值
    if position == "buttom":
        try:
            if index + 3 in [3, 4, 5, 6, 7, 8]:  # 若index+3 在此列表中，则为有值
                return array[index+3]
        except IndexError:
            return None

    if position == "over":
        try:
            if index - 3 in [0, 1, 2, 3, 4, 5]:
                return array[index-3]
            else:
                return None

        except IndexError:
            return None

    if position == "right":
        try:
            if index+1 in [1, 2, 4, 5, 7, 8]:
                return array[index+1]
        except IndexError:
            return None

    if position == "left":
        try:
            if index-1 in [0, 1, 3, 4, 6, 7]:
                return array[index-1]
            else:
                return None
        except IndexError:
            return None


def getBesides(array: list, present: int) -> list:
    # 获取所有相邻的值

    listName = []  # 创建一个用于储存相邻值的列表

    over = outPut(array, present, 'over')  # 获取上边的值
    listName.append(over)  # 将值添加到列表里

    left = outPut(array, present, "left")  # 获取左边的值
    listName.append(left)  # 将值添加到列表里

    right = outPut(array, present, "right")  # 获取右边的值
    listName.append(right)  # 将值添加到列表里

    buttom = outPut(array, present, "buttom")  # 获取下边的值
    listName.append(buttom)  # 将值添加到列表里

    if a == 0:
        # 去除None
        while True:
            if None in listName:
                listName.remove(None)
            else:
                break

    return listName


def move(array: list, target: int, willmoved: int):
    # 移动
    targetIndex = getIndex(array, target)
    willmovedIndex = getIndex(array, willmoved)
    array[targetIndex], array[willmovedIndex] = willmoved, target


def main(array: list, startnum: int, target: list):
    if issolution(array) == issolution(target):

        rode = []  # 创建队列
        for i in getBesides(array, startnum):  # 将startnum的所有邻值作为起始值
            rode.append(i)

        while rode:  # 若rode中还有值，则循环
            #
            # 可选，记录一共查找了多少此
            global count
            count += 1
            #

            # 移动
            if (array == target):  # 若初始状态为目标状态
                return "这就是解"

            roded = rode.pop(0)  # 弹出最左边的值
            if type(roded) == int:  # 若roded是整型，直接移动
                move(array, roded, startnum)

            else:  # 若roded是列表型，for遍历roded中的值并移动
                for j in roded:
                    move(array, j, startnum)

            if (array == target):  # 再次判断
                array = arrCopied

                return roded
            else:  # 添加最后一个值的除了前一个值的所有邻值
                for i in getBesides(array, startnum):
                    # i 是int 类型

                    if type(roded) == int:  # int类型不是可迭代对象，不能之间转化为列表
                        if i != roded:  # 判断是不是前一个值
                            bufferList2 = []
                            bufferList2.append(roded)
                            bufferList2.append(i)
                            rode.append(bufferList2)
                            # print(bufferList2)
                            del bufferList2

                    elif type(roded) == list:
                        if i != roded[-1]:
                            bufferList = []
                            bufferList.append(i)
                            rode.append(roded+bufferList)
                            # print(roded+bufferList)
                    else:
                        if i != roded[-1]:
                            rode.append(roded + i)

            array = arrCopied.copy()  # 重置列表
    else:
        array = arrCopied
        return "无解"

print(_data.array_buffer)
time_begin = time.time()
b = main(array, 0, target)
if b == '无解' :
    result = "无解"
else :
    array = arrCopied.copy()
    result = name_move(array, 0, b)
time_end = time.time()
print("所用时间为：",time_end-time_begin)
print(result)
